package singleList;

import myexception.ListIndexOutOfBoundsException;
import listinterface.IList;

public class MySingleList implements IList {
    //静态内部类 ， 可通过 外部类类名.静态内部类类名拿到
    public static class ListNode {
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

    public ListNode head;//表示当前节点的头节点

    public int listSize;


    // 手动创建一个链表
    public void creatList() {
        //创建 5 个节点
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }

    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //已经涵盖了下面的特殊情况
        node.next = head;
        head = node;
        listSize++;
//        if (head ==null){
//            head = node;
//        } else {
//            //对于插入来说一般建议 ， 先绑定后面的节点 ， 这样数据就不容易丢失
//            node.next = head;
//            head = node;
//        }
    }

    @Override
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        //表示列表为空
        if (head == null) {
            head = newNode;
            listSize++;
            return;
        }
        ListNode cur = head;

        while (cur.next != null) {

            cur = cur.next;
        }
        cur.next = newNode;
        listSize++;

    }

    @Override
    public void addIndex(int index, int data) throws ListIndexOutOfBoundsException {
        //考虑传入下标的合法性
        checkIndexOdAdd(index);

        ListNode node = new ListNode(data);

        //考虑 index = 0 的情况
        if (index == 0) {
            addFirst(data);
        }
        //考虑 index 是最后一个下标的情况
        if (index == size()) {
            addLast(data);
        }

        ListNode cur = findIndex(index);

        node.next = cur.next;

        cur.next = node;

        listSize++;

    }

    //写一个方法找到 index-1 下标对应的地址
    private ListNode findIndex(int index) {
        ListNode cur = head;
        int count = 0;
        if (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //写一个方法判断 ， 当前传入的 index 是否合法
    private void checkIndexOdAdd(int index) {
        if (index < 0 || index > size()) {
            throw new ListIndexOutOfBoundsException("插入Index的位置不合法");
        }
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if (head == null) {
            return;
        }
        if (head.val == key) {
            head = head.next;
            return;
        }
        ListNode node = findNode(key);
        if (node == null) {
            System.out.println("没有你要删除的数据");
            return;
        }
//        ListNode del = new ListNode(key);
        ListNode del = node.next;
        node.next = del.next;
    }

    //找到第一个 key 的前一个节点
    //m没有找到返回 null
    private ListNode findNode(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    @Override
    public void removeAllKey(int key) {
        //如果头节点为空 ， 则没有元素要删除 ， 直接跳出函数
        if (head == null) {
            return;
        }
//        while(head.val == key) {
//            //如果删除后每一个头节点都是要删除的元素 ， 循环可以确保没有遗留
//            head = head.next;
//        }
        ListNode cur = head.next;
        ListNode prev = head;

        while (cur != null) {
            if (cur.val == key) {
                prev = cur.next;
                cur = cur.next;
                listSize--;
            } else {
                prev = cur;
                cur = cur.next;
            }

        }
        if (head.val == key) {
            head = head.next;
            listSize--;
        }
    }

    @Override
    public int size() {
        //求列表有几个节点
//        ListNode cur = head;
//        int count = 0;
//        while(cur != null){
//            count++;
//            cur = cur.next;
//        }
//        return count;
        return listSize;
    }

    public ListNode reverse() {

        if (head == null) {
            return null;
        }
        //只有一个节点
        if (head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNex = cur.next;
            cur.next = head;
            head = cur;
            cur = curNex;
        }
        return head;
    }

    @Override
    public void clear() {
        head = null;
        listSize = 0;
    }

    @Override
    public void display() {
        //
        ListNode cur = head;
        while (cur != null) {
            System.out.println(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //从指定节点开始打印
    public void display2(ListNode newHead) {
        //
        ListNode cur = newHead;
        while (cur != null) {
            System.out.println(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //返回链表的中间节点
    //方法一：
//    public ListNode middleNode(){
//        if (head == null){
//            return head;
//        }
//        int len = size();
//        int index = len/2;
//        ListNode cur = head;
//        while(index != 0 ){
//            cur = cur.next;
//            index--;
//        }
//        return cur;
//    }

    //方法二；
    public ListNode middleNode() {

        if (head == null) {
            return null;
        }
        //路程一样时 ， 快的速度是慢的速度的2倍 ， 当快的到达重点时 ， 速度慢的那一个正好在整个路程的中间位置
        //注意七点要一样
        ListNode fast = head;
        ListNode slow = head;
        //下面的两个条件不能互换 fast.next != null && fast != null
        //如果 fast 为空这里就空指针异常了
        //而下面这种写法 ， 如果 fast 为空就短路与 ， 不会执行后面的代码
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;

    }
        //传入一个链表 ， 返回倒数第 k 个节点 ， 如何在不求长度的情况下得到结果
        //让 fast 先走 k-1 步；然后 slow 和 fast 同时走 ； fast 走到最后的时候 ， slow 所指的节点就是倒数第 k 个节点
    public int KthToLast(int k){
        int len = size();
        if (k<=0 && k>len){
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
//        for (int i = 1; i < k-1; i++) {
//            fast = fast.next;
//        }
        int count = 0;
        while(count != k-1){
            fast = fast.next;
            count++;
        }
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow.val;
    }

    //将两个升序链表合并为一个新的升序链表并返回， 新链表是通过拼接给定两个链表的所有节点组成的
    /*
    思路：
    设两个链表的头节点为 headA 和 headB ， 然后再创建一个新的头节点 newH ，
     */

    //判断一个个链表是否是回文
    public boolean chPalindrome(ListNode list){
        if(head ==null){
            return false;

        }
        if (head.next ==null){
            return false;
        }
        //找出中间节点
        ListNode fast = head;
        ListNode slow = head;
        if(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //将链表后半部分反转
        ListNode cur = slow.next;
        while (cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow.next = cur;
            cur = curN;
        }
        //判断是否是回文
        while(head != slow){
            if (head.val != slow.val){
                return false;
            }
            //判断偶数情况
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return false;
    }

    //相交链表找到相交节点
    public ListNode getIntersectionNode(ListNode headA,
                                        ListNode headB){
        ListNode pl = headA;
        ListNode ps = headB;

        int len1 = 0;
        int len2 = 0;

        while(pl != null){
            len1++;
            pl = pl.next;
        }
        while(ps != null){
            len2++;
            ps = ps.next;
        }
        //修改指向 ， 使pl ps 分别指向各自的头节点
        pl = headA;
        ps = headB;

        int len = len1 - len2;

        if (len < 0){
            //headB 比 headA 长 交换 pl ps的指向
            pl = headB;
            ps = headA;
            len =len2 - len1;
        }
        while(len!=0){
            pl = pl.next;
            len--;
        }
        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        //如果没有相遇
        if (pl ==null){
            return null;
        }
        return pl;
    }

    //判断是否是环形链表
    private boolean hasCycle(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
    //找到环形链表环的入口 力扣 142
    public ListNode detectCycle(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        //找到第一次相遇的jiedian
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        if (fast == null || fast.next ==null){
            return null;
        }
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
    //创建一个环形链表
    public void createLoop(){
        ListNode cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = head.next.next.next;
    }



}
